import java.util.Arrays;

/**
 * 面试题 16.16. 部分排序
 * https://leetcode-cn.com/problems/sub-sort-lcci/
 */
public class Solutions_mianshi_16_16 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19};  // output: {3, 9}
//        int[] nums = {9, 1, 2, 3, 4, 5};  // output: {0, 5}

        int[] result = subSort(nums);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解法三：逆序对思想（ms）
     */
    public static int[] subSort(int[] array) {
        int[] res = {-1, -1};
        if (array == null || array.length <= 1) {
            return res;
        }
        int len = array.length;
        int left = -1, right = -1;
        int max = array[0];
        // 从左往右，找到部分排序的右端点
        for (int i = 1; i < len; i++) {
            if (array[i] >= max) {
                // 重新定义最大值
                max = array[i];
            } else {
                // 右侧出现较小值，那么 [?, i] 区间是一定要进行排序的
                right = i;
            }
        }
        if (right == -1) {
            return new int[]{left, right};
        }
        int min = array[len - 1];
        // 从右往左，找到部分排序的左端点
        for (int i = len - 2; i >= 0; i--) {
            if (array[i] <= min) {
                min = array[i];
            } else {
                left = i;
            }
        }
        return new int[]{left, right};
    }

    /**
     * 解法二：排序 + 线性遍历（22ms）
     */
    public static int[] subSort3(int[] array) {
        int[] res = {-1, -1};
        if (array == null || array.length <= 1) {
            return res;
        }
        int[] clone = array.clone();
        Arrays.sort(clone);
        int len = array.length;
        // 克隆数组后，一一比较元素
        for (int i = 0; i < len; i++) {
            if (array[i] != clone[i]) {
                if (res[0] == -1) {
                    res[0] = i;
                }
                res[1] = i;
            }
        }
        return res;
    }

    /**
     * 解法一：排序 + 两遍遍历（22ms）
     */
    public static int[] subSort2(int[] array) {
        int[] res = {-1, -1};
        if (array == null || array.length <= 1) {
            return res;
        }
        int[] copyNums = array.clone();
        Arrays.sort(copyNums);
        int len = array.length;
        int i = 0;
        // 从左向右，定位到左侧不同的位置
        for (; i < len; i++) {
            if (array[i] != copyNums[i]) {
                break;
            }
        }
        if (i == len) {
            // 数组本身有序
            return res;
        }
        res[0] = i;
        i = len - 1;
        // 从右向左，定位到右侧不同的位置
        for (; i > res[0]; i--) {
            if (array[i] != copyNums[i]) {
                break;
            }
        }
        res[1] = i;
        return res;
    }
}
